// https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/

package main


// 非递归形式
/**
* Definition for a Node.
* type Node struct {
*     Val int
*     Children []*Node
* }
*/

func preorder(root *Node) []int {
	rst := make([]int, 0)
	if root == nil {
		return rst
	}
	// 定义显示栈
	stack := []*Node{root}

	for len(stack) > 0 {
		n := len(stack)
		// 拿到当前元素
		node := stack[n-1]
		stack = stack[:n-1]
		rst = append(rst, node.Val)
		// 逆序加入
		for i := len(node.Children) - 1; i >= 0; i--{
			stack = append(stack, node.Children[i])
		}
	}

	return rst
}



// 递归形式
func preorder(root *Node) []int {
	rst := make([]int, 0)
	var dfs func(*Node)
	// 深度优先遍历
	dfs = func(node *Node) {
		if node == nil {
			return
		}
		// 头结点处理
		rst = append(rst, node.Val)
		// 深度
		for _, node := range node.Children {
			dfs(node)
		}
	}

	dfs(root)
	return rst
}